8. 亲子游戏

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let lines = [];
class Node {
    constructor(x,y,ca,steps) {
        this.x = x;
        this.y = y;
        this.ca = ca;
        this.steps = steps;
    }
}
rl.on('line', (line) => {
    lines.push(line);
});
rl.on('close', () => {
    let n = parseInt(lines.shift());
    let grid = lines.map(item => item.split(' ').map(Number));
    const visited = Array.from({length: n}, () => Array.from({length: n}, () => [-1, -1]));
    let start = null
    maxCa = 0;
    const queue = [];
    for(let i=0; i<n; i++) {
        for(let j=0; j<n; j++) {
            if(grid[i][j] === -3) {
                start = new Node(i, j, 0, 0);
                visited[i][j] = [0, 0];
                break;
            }
        }
    }
    queue.push(start);
    let flag = 0;
    let dx = [-1, 0, 1, 0];
    let dy = [0, 1, 0, -1];
    while(queue.length > 0) {
        const current = queue.shift();
        if (grid[current.x][current.y] === -2) {
            flag = 1;
            maxCa = Math.max(maxCa, current.ca);
            continue;
        }
        for(let i=0; i<4; i++) {
            const nx = current.x + dx[i];
            const ny = current.y + dy[i];

            if (nx >= 0 && nx < n && ny >=0 && ny < n && grid[nx][ny] !== -1) {
                const newCa = current.ca + grid[nx][ny];
                const newSteps = current.steps + 1;
                if (visited[nx][ny][0] === -1 || visited[nx][ny][0] > newSteps || (visited[nx][ny][0] === newSteps && visited[nx][ny][1] < newCa)) {
                    visited[nx][ny] = [newSteps, newCa];
                    queue.push(new Node(nx, ny, newCa, newSteps));
                }
            }
        }
    }
    if (!flag) {
        maxCa = -1;
    }
    console.log(maxCa >= 0 ? maxCa : -1);

});